The present invention relates to the field of programmable devices, and the systems and methods for programming the same. Programmable devices, such as FPGAs, typically includes thousands of programmable logic cells that use combinations of logic gates and/or look-up tables to perform logic operations. Programmable devices also include a number of functional blocks having specialized logic devices adapted to specific logic operations, such as adders, multiply and accumulate circuits, phase-locked loops, and memory. The logic cells and functional blocks are interconnected with a configurable switching circuit. The configurable switching circuit selectively routes connections between the logic cells and functional blocks. By configuring the combination of logic cells, functional blocks, and the switching circuit, a programmable device can be adapted to perform virtually any type of information processing function.
A typical process for determining the configuration of a programmable device, referred to compilation, starts with an extraction phase, followed by a logic synthesis phase, a fitting phase, and an assembly phase. The extraction phase takes a user design, typically expressed as a netlist in a hardware description language such as Verilog or VHDL, and produces a set of logic gates implementing the user design. In the logic synthesis phase, the set of logic gates is permuted over the hardware architecture of the programmable device in order to match elements of the user design with corresponding portions of the programmable device. The fitting phase assigns the various portions of the user design to specific logic cells and functional blocks (sometimes referred to as placement) and determines the configuration of the configurable switching circuit used to route signals between these logic cells and functional blocks (sometimes referred to as routing), taking care to satisfy the user timing constraints as much as possible. In the assembly phase, a configuration file defining the programmable device configuration implementing the user design is created. The programmable device configuration can then be loaded into a programmable device to implement the user design. Programmable devices can be configured with the configuration during or after manufacturing.
One of the substantial challenges of the logic synthesis phase is the optimal representation of the user design of the sequential circuit. FIG. 1 illustrates an example sequential circuit. In a sequential circuit 100, there exists combinational logic 110, such as AND, OR, and other types of gates, and registers 120. Registers store the current state of the sequential circuit 100. The next state of the sequential circuit 100 may depend on the current state and/or on inputs to the circuit. Often, the logic synthesis phase strives to implement portions of the user design with as few registers and combinational logic gates as possible in order to get a more efficient design or implementation. The search for reducible registers is important for this goal of reducing the number of registers and logic elements.
Examples of reducible registers are “stuck-at” or “duplicate” registers. In some circuits, a register value may never change regardless of the inputs or the current state of the sequential circuit, and thus the register is “stuck-at” the value with which it powers up. Other register values are “duplicates,” if they are set to identical values at power up and continue to carry identical values for every possible current state and input combination to the sequential circuit. Registers that have opposite values and continue to carry opposite values are also considered “duplicates.” Reducible registers and associated logic can be removed to simplify the sequential circuit.
Some optimization methods use Boolean analysis to identify reducible registers. Although robust and accurate, these methods are quite slow when the number of inputs and registers is large. Other methods use random simulation methods to test the functional equivalence of hardware designs. These random simulation methods randomly select input values to test the outputs of different circuits. To verify functional equivalence, the random simulation methods require an exhaustive search of all input values to avoid leaving large portions of a sequential circuit untested. Additionally, these prior “functionally equivalent” approaches are limited to evaluating the equivalence of combinational circuits already identified for optimization. They do not identify possible areas of a circuit to be optimized.
It is therefore desirable to have a fast and efficient system and method to optimize a sequential circuit. It is further desirable for the system and method to quickly screen out registers that are not likely to be reducible. It is also desirable for the system and method to efficiently identify and verify reducible registers given a user specified sequential circuit.